Recently, significant press coverage has focused on attacks to computers and databases owned by private users and especially by government entities or private corporations. Attackers involved in such attacks (who may also be referred to as “intruders”) can be differentiated into two types, according to whether the attacker uses digital messages from a remote location to perform the attack (whom we can call “external attackers”) or the attacker uses digital messages from a location within the same entity that is attacked (whom we can call “internal attackers” or “insiders”). Partially motivated by this coverage of intrusions from both external attackers and insiders into databases containing highly sensitive information, this invention includes cryptographic protocols in the presence of intruders, under a novel and reasonable assumption on their power. This leads to a new investigation model, which is referred to as the Bounded Retrieval Model, since one of its major features of the model is that of assuming the existence of an upper bound on the amount of a party's stored data that can be retrieved by the attacker or adversary. In practice, this bound would be due to both physical and logical considerations. With respect to internal attackers, this upper bound may result from the capabilities of a simple Intrusion Detection System (IDS), which only needs to be capable of monitoring any large and repeated access to the party's stored data. With respect to external attackers, this upper bound is further minimized as a consequence of the inherent gap between the smaller availability of the communication bandwidth due to physical limits of the communication channel and the larger availability of storage memory: an attacker needing a large amount of time to retrieve large amounts of sensitive data will most likely be unable to maintain an unauthorized connection for enough time without being detected.
The model could be considered a non-trivial variation of the well-studied Bounded Storage Model, introduced in Ueli Maurer, Conditionally-Perfect Secrecy and a Provably-Secure Randomized Cipher, Journal of Cryptology, vol. 5, no. 1, pp. 53-66, 1992. In Stefan Dziembowski and Ueli Maurer, Optimal Randomizer Efficiency in the Bounded-Storage Model, in Journal of Cryptology, vol. 17, no. 1, pp. 5-26 and the references therein further studies of several cryptographic tasks, such as key-agreement, encryption, oblivious transfer, and time-stamping, etc are described. The present model postulates a fixed upper bound on the storage capacity, but no bound at all on the computational power, of the adversary attacking a cryptographic protocol. Thus, with respect to the standard investigation model used in the cryptography literature, where the upper bounds on the attacker's storage and computational power are uniquely due to current technological limitations on both storage and computational power (often referred to as “polynomial in the security parameter” in the literature), the Bounded Storage Model achieves much higher security at the expense of a stronger assumption on the adversary's storage capability. Namely, it assumes a fixed upper bound on storage capacity that may be smaller than what is indicated by current technological limitations. Analogously, the bounded retrieval model also avoids fixed upper bounds on the computational power of the adversary at the expense of a stronger assumption on the adversary's retrieval capability. Namely, it assumes a fixed upper bound on retrieval capacity that may be smaller than what is indicated by current technological limitations. However, this retrieval assumption is supported by more specific technological considerations related to the availability of an IDS and/or to the gap between communication bandwidth and storage memory.
The importance of securing the server password file has been well-known for many years, and is discussed in detail, for instance, in N. Provos and D. Mazieres, A Future-Adaptable Password Scheme, in Proceedings of the Annual USENIX Technical Conference, 1999 and in D. C. Feldmeier and P. R. Karn, UNIX Password Security—Ten Years Later, in Proceedings of Crypto '89, LNCS, no. 435, Springer-Verlag, pp. 44-63. Various aspects of password protocols have been studied in the security literature. One important area is that of securing password protocols where the communication goes over an insecure network as described in, e.g., S. Halevi and H. Krawczyk, Public-key Cryptography and Password Protocols, in Proc. of the 5th annual ACM conference on Computer and Communications Security, pp. 122-131, 1998 for schemes based on public-key encryption and S. Bellovin and M. Merrit, Encrypted Key Exchange, in Proc. of the 1992 Internet Society Network and Distributed System Security Symposium; S. Bellovin and M. Merrit, Augmented Encrypted Key Exchange, in Proc. of the 1st ACM Conference on Computer and Communication Security}, pp. 224-250; S. Patel, Number theoretic attacks on secure password schemes, in Proc. of the 1997 IEEE Symposium on Security and Privacy; and T. Wu, The secure remote password protocol, in Proc. of the 1998 Internet Society Network and Distributed System Security Symposium for heuristic schemes not using public keys.